public class Test3 {        //逻辑控制完+方法
    public static void main(String[] args) {
        //System.out.println(fib(5));
        System.out.println(fib2(5));
        System.out.println(fib2(40));
    }

    public static int fib(int n) {                //用 递归 的方式求 第n个斐波那契数
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);     //多路递归，产生很多重复计算
    }

    public static int fib2(int n) {               //用非递归：循环（迭代）的方式求 第n个斐波那契数
        if (n == 1 || n == 2) {
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }



    public static void main4(String[] args) {
        System.out.println(sum1(123));
    }

    public static int sum1(int n) {               //输入一个非负整数，返回组成它的数字之和
        if(n < 10) {
            return n;
        }
        return n % 10 + sum1(n / 10) ;
    }





    public static void main3(String[] args) {
        System.out.println(sum(5));
    }

    public static int sum(int n) {              //递归求 1~n 的和
        if(n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }





    public static void main2(String[] args) {
        //System.out.println(fac(3));
        func(123);
    }

    public static int fac(int n) {              //递归求n的阶乘
        if(n == 1) {
            return 1;
        }
        return n * fac(n - 1);
    }

    public static void func(int n) {            //使用递归顺序打印出一个整数的每一位
        if(n < 10) {
            System.out.print(n + " ");
            return;
        }
        func(n / 10);
        System.out.print(n % 10 + " ");
    }





    public static void main1(String[] args) {    //StackOverflowError 栈溢出错误
        func();
    }

    public static void func() {                  //递归的错误示范
        func();
    }

}
